\documentclass[a4paper,10pt,ar]{article}
%% Paquetes utilizados%%
\usepackage{amssymb}
\usepackage{graphicx}
%% Fancy Headers %%
%\pagestyle{plain}

\usepackage{fancyhdr}
\usepackage{url}

\pagestyle{fancy}
\fancyhf{}
\fancyhead[LE,LO]{C\'alculo de raices mediante esquemas iterativos de Punto Fijo}
\fancyhead[RE,RO]{\thepage}
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0pt}
\fancypagestyle{plain}{
\fancyhead{}
\renewcommand{\headrulewidth}{0pt}
}
%% Datos del Autor, fecha, etc %%
\author{Gonzalo Bellver, Germ\'an Gross, Juan Mart\'in Pampliega}
\title{Criptograf\'ia y Seguridad￼\linebreak Trabajo Pr\'actico $N^{o}$ 1}
\date{March 31, 2009}
\begin{document}
\maketitle
\begin{center}
\textbf{Resumen}
En el siguiente trabajo, se presentan estrategias, soluciones, y algoritmos implementados en C, que permiten descrifrar mensajes en castellano, cifrados con m\'etodos de encriptaci\'on cl\'asica: sustituci\'on simple, sustituci\'on polialfab\'etica y Trasposici\'on.
\end{center}
\bigskip

\section{Introducci\'on}
EL objetivo principal del trabajo consiste en descifrar tres textos, que fueron encriptados con tres m\'etodos distintos: el \textbf{m\'etodo de C\'esar}, \textbf{Vigenere} y \textbf{tansposici\'on por columnas}.
\\\\Es por esto que el primer problema que se presenta es identificar, de forma autom\'atica, qu\'e algoritmo fue utilizado en cada texto. Una vez logrado, se proceder\'a a romper dicha encriptaci\'on para poder leer el mensaje original, sin necesidad de conocer la clave utilizada para cifrar el mismo.

\section{Identificando el algoritmo de encriptaci\'on}
Para identificar el algoritmo de encriptaci\'on se utiliz\'o el m\'etodo descripto por Friedman, W.F. en una publicaci\'on titulada \emph{The index of coincidence and its applications in cryptology.}.
\\\\El mismo se basa en comparar un texto contra s\'i mismo, pero rotado. Si los \emph{\'indices de coincidencias} son en su mayor\'ia cercanos al $0.03$, o sea, cercanos a la distribuci\'on aleatoria, entonces el texto fue encriptado con \textbf{Vigenere}, ya que este es el \'unico m\'etodo que afecta las estad\'isticas del lenguaje.
\\\\Si por el contrario, los \emph{\'indices de coincidencias} son mayoritariamente cercanos al $0.07$, o sea, al del idioma castellano, el texto fue encriptado con el \textbf{m\'etodo de C\'esar} o con \textbf{transposici\'on por columnas}.
\\\\Para distinguir entre ambos, simplemente chequeamos la frecuencia de aparcici\'on de las letras. Si se corresponden con las del idioma espa\~{n}ol, entonces se trata de \textbf{transposici\'on por columnas}, ya que este m\'etodo no afecta la frecuencia de aparici\'on de los caracteres. En cambio si la frecuencia no se corresponde con las del idioma, nos encontramos frente a un \textbf{C\'esar}.

\section{Descifrando Cesar y Vigenre}
Ambos algoritmos se tratan en la misma secci\'on, ya que el \textbf{m\'etodo del C\'esar} es una versi\'on debilitada del \textbf{m\'etodo de Vigenere}, ya que encriptar algo con el \textbf{m\'etodo del C\'esar} es exactamente igual a encriptarlo con \textbf{Viegenere} utilizando una clave de longitud uno. Es por esto, que al primer m\'etodo vamos a considerarlo simplemente un caso particular del segundo.
\\\\El primer problema cuando atacamos \textbf{Vigenere} consiste en averiguar la longitud de la clave. Para esto utilizaremos nuevamente el ataque por \emph{\'indice de coincidencias}. Para averiguar la longitud deseada, simplemente compararemos el texto cifrado contra s\'i mismo, pero rotado. El \emph{\'indice de coincidencias} ser\'a siempre cercano al $0.03$, debido a que se aproximar\'a a una distribuci\'on aleatoria. Esto se cumplir\'a en todos los casos excepto cuando el n\'umero de rotaciones sea m\'ultiplo de la longitud de la clave. En este caso, el \emph{\'indice de coincidencias} ser\'a cercano a $0.07$, ya que cuando el n\'umero de rotaciones sea m\'ultiplo de la longitud de la clave, los caracteres encriptados con las mismas letras estar\'an alineados, por lo que el \emph{\'indice de coincidencias} deber\'a coincidir con el del idioma castellano (que es aproximadamente $0.07$). Esto se debe a que los caracteres encriptados con la misma letra conservan entre s\'i las estad\'isticas del lenguaje.
\\\\Una vez obtenida la longitud de la clave, para descifrar los textos se utiliz\'o el algoritmo descripto en \url{http://islab.oregonstate.edu/koc/ece575/02Project/Mun+Lee/VigenereCipher.html#encryption_decryption}.
\\\\Este algoritmo se basa en el hecho de que cuando utilizamos \textbf{Vigenere}, como se explic\'o anteriormente, los caracteres encriptados con las mismas letras, conservan estad\'isticas del lenguaje. Aprovechando esto, agrupamos todos los caracteres que se encuentran en la misma posici\'on dentro de cada grupo. Esto nos asegura que este conjunto de caracteres, tendr\'a las mismas caracter\'isticas estad\'isticas del idioma en el cual fue escrito el mensaje.
\\\\Haciendo uso de esto, y conociendo la frecuencia de las letras del idioma espa\~{n}ol, averiguamos el n\'umero de rotaciones que se aplica a cada posici\'on dentro de cada grupo y as\'i obtenemos la clave utilizada para encriptar.

\section{Descifrando Transposici\'on}
Para la resoluci\'on del m\'etodo de transposici\'on se consider\'o el m\'etodo de transposici\'on por columnas con intercambio del orden de las columnas de la matriz generada seg\'un una clave.
\\\\Para averiguar la clave se fueron considerando claves de tama\~{n}o creciente entre 1 y 10. Se arma la matriz correspondiente al texto cifrado seg\'un el largo de la clave considerada. Luego se utiliza una caracter\'istica del lenguaje castellano que es que siempre que hay una letra ``q'' debe estar seguida de una letra ``u''. Esta caracter\'istica se utiliza para descartar posibles largos de claves buscando en la matriz generada a partir del texto letras ``q'' y cercior\'andonos de encontrar letras ``u'' en su misma fila o en la siguiente, ya que debe ser parte del mismo bloque o el que viene a continuaci\'on. Si se observa que no ocurre esto el largo posible de la clave se descarta.
\\\\Una vez que se encuentra un largo posible se generan las posibles claves para ese largo limitando la lista por b\'usqueda de anagramas en bloques donde est\'en las ``q''. Se prueba con cada clave desencriptar el texto transponiendo la matriz que se tiene a la original seg\'un la clave. De los textos obtenidos nuevamente se utiliza la la caracter\'istica de que si se tiene en el texto una ``q'' si una ``u'' despu\'es, el texto se descarta. Finalmente de los textos no descartados se cuentan la cantidad de bigramas frecuentes en castellano como ``es'' y ``de'' y el que mayor de estos bigramas posee es el texto que se presenta como soluci\'on.
\\\\Es importante notar que al principio del proceso se reemplazan las ``\~{N}'' y ``\~{n}'' presentes en el texto, antes de formar la matriz, por ``\}'' y ``\{'' respectivamente. Esto se hace para facilitar la manipulaci\'on de la matriz y no tener casos especiales ya que \'estas letras ocupan 2 bytes cuando se recibe el texto como argumento por l\'inea de comando. 
\\\\Los m\'etodos utilizados pueden no llegar a ser los \'optimos pero esto se debe a que no hay un m\'etodo concreto de ataque a este tipo de encriptaci\'on como si hay en el caso de Vigenere o C\'esar.

\section{Los Textos Descifrados}
El primer texto:
\\\\DSENMEUIRONSIUEDNADAOURUUNQPSSTEADDAADLOJNSYELOR
\\MNISSNOAORLAVNISETTSSACLRESQARDDEMMZQOLENUUAPINI
\\DILNCACRQNFPEEYOOALSNREAUOIOTIOSSUDSDASAOYUTERNN
\\ATVEDNNAAFTUOUYOXSEIRBOOSOACNROQEACLESANADCLTACL
\\QDERSODIEENPUNAOOSUPOUBALANEBOODRIEVSIMOEUAIARLR
\\SNYLDSOMNAMOCENRURIOERDLDONOLVATDOISOEAPHROENFCD
\\IACADICSDREUOAGUSSUFNURECEIOORUFUASEEUEOGVTEEETO
\\APCOAERGAPDLINSEAORAONISSESCRVHOSSOOICNOTLBSOMOA
\\SOALNDEEEFMMOISAENDGPRTEAIQREREAGLUSEAOTEFCETTAE
\\TQERTFEXAPNNDLEREBQGPNPNOEORRNELDUHCCHARCOIONTPS
\\QSRRECLQTEUIAAAGEERRAUDDEERENEEZLLSUOELSCRIAYEUC
\\SCARROORBDUIRIDSECAUQCMISOHNOASNAUNAORATBECEEONA
\\LAUARAREARSAALNVIEOORADOADRSEIOCUOOLNUFUARMEPRMO
\\LRAOSREOLSESSNNOAELCFSOPOELRLRCODEDAIFRPIOEASRIL
\\NATNUOOEUROTQNTOBETNNICRAROSSSTNENEROVISEMDNYOII
\\OSTMEBOSVISCRFDUEEYELEREBAANRLBAOVNTTREDOEDTTTSN
\\BDAIIPSIMCLOEOUMESECSUTEATNEEMAACBRAEMEMMTSAUTAL
\\ACACCOCANDMTACACQAELPIVYNOEZACEDSDIEEIMQEAEAOIIB
\\LNSPONALANSTEERDSADRRISUSLEUAEUEIORORUCDEIONSNLI
\\ELLIIEUTSAOXAAASIOOTHINPEUUSEODENIMOEUIÑDEIRLIMO
\\UNNOUDALTMEABUNADEENRAIURHQRSCAROCAESTNENUUESDEI
\\CROEAETRCNDVNSCNO
\\\\El mismo fue encriptado utilizando transposici\'on por columnas con clave \textbf{23456781}.
\\El texto desencriptado es el siguiente:
\\\\USLABIDUROLEDOSDIASLARESOLUCIONDENOFIRMARDESPUES
\\DELOSCUALESPIDIODECOMERYOFRECIOUNMILLONTOMARONSE
\\LOYLESIRVIERONUNASUCULENTACOMIDADESDEENTONCESLAV
\\IDADELDESGRACIADOPRISIONEROFUEUNATORTURAPERPETUA
\\HABIASUFRIDOTANTOQUENOQUERIAEXPONERSEASUFRIRMASY
\\CEDIAATODASLASEXIGENCIASALCABODECUATRODIASUNATAR
\\DEQUEHABIACOMIDOCOMOENLOSTIEMPOSDESUMEJORFORTUNA
\\ECHOSUSCUENTASYNOTOQUEERATANTOLOGASTADOQUENOLERE
\\STABANMASQUECINCUENTAMILFRANCOSENTONCESSUFRIOUNA
\\REACCIONEXTRAÑAACABANDODEPERDERCINCOMILLONESTRAT
\\ODESALVARLOSCINCUENTAMILFRANCOSQUELEQUEDABANANTE
\\SQUEENTREGARLOSSEPROPUSOUNAVIDADEPRIVACIONESYLLE
\\GOAENTREVERMOMENTOSDEESPERANZAQUERAYABANENLOCURA
\\TENIENDOOLVIDADOADIOSDESPUESDEMUCHOTIEMPOCOMENZO
\\ACREERQUEHABIAOBRADOMILAGROSQUELACAVERNAPODIAHUN
\\DIRSEQUELOSCARABINEROSPONTIFICIOSPODIANDESCUBRIR
\\AQUELODIOSOENCIERROYSALVARLEPENSOENLOSCINCUENTAM
\\ILFRANCOSQUELERESTABANQUEERANUNASUMASUFICIENTEPA
\\RAPRESERVARLEDELHAMBREYROGOADIOSSELOSCONSERVARAY
\\ORANDOLLOROTRESDIASTRANSCURRIERONDEESTEMODODURAN
\\TELOSCUALESELNOMBREDEDIOSESTUVOCONSTANTEMENTESIN
\\OENSUCORAZONENS
\\\\\\El segundo texto:
\\\\OIRACRYGRBCFOIHHCAQIQCYRFRDITAÑOÑYÑVQRÑQRJRGHVFÑ
\\GIUVWCPCAFCDÑQRUCZOFRGVDCFRWRZDYCDIQVRFÑRAPCAHFÑ
\\FIAHFÑWRQRPUVPCTFÑAQRZIMTFÑAQRDCQFVÑPCFHÑFÑEIRYY
\\ÑYÑFTÑMUCFFVOYROÑFOÑMHRBVFYÑGPÑAÑGÑGVPCAGRTIVFVÑ
\\QVGVZIYÑFYCGDRCFRGQRHÑYYRGMPCAGRFJÑFÑYTCQRGIQVTA
\\VQÑQDCFACZRAPVCAÑFGIDCGVPVCAGCPVÑYRAOÑYHVZCFRDRF
\\CYÑOIGEIRQÑÑSÑACGÑDCFYÑGRPPVCAQRPUVPCGSIRVAIHVYA
\\CRAPCAHFCFCDÑÑQRPIÑQÑDÑFÑRYOIHHCAEIRÑPÑOÑOÑQRAÑP
\\RFFCTRFOIHHCAYRRPUÑOÑYÑPIYDÑÑYÑHVRAQÑPYÑFCRGHÑRA
\\GRZRWÑAHRGPÑGCGYCÑDFCDVÑQCRGRPUÑFYRYÑPIYDÑÑYÑHVR
\\AQÑEIRRQÑQZRUÑQVPUCEIRHVRARGIUVWCDFRTIAHCRYQRDRA
\\QVRAHRPCAPIFVCGVQÑQHVRARQVRPVGRVGÑBCGÑUDRFQCARUÑ
\\OVÑRAHRAQVQCGRVGUCFÑGRAPCAHFÑFÑYÑGRPPVCAQRWCJRAR
\\GRARYGVTIVRAHRDÑGVYYCRYGRBCFOIHHCAGRÑYRWCPCAÑVFR
\\HFVGHRQRFRDRAHRGRDÑFCFÑQVÑAHRMGRBÑYCPCARYQRQCUÑP
\\VÑIAZÑAVEIVQRYRGPÑDÑFÑHRÑEIRYRLPYÑZCZRYYRJCRGRHF
\\ÑWRRYEIRYYRJÑRYZÑAVEIVRYQRDRAQVRAHRYCZVFCÑGCZOFÑ
\\QCDRFCUCZOFRDFCHRGHCRGRACRGIAHFÑWRDÑFÑPUVPCGDCQF
\\VÑDCARFGRYCIAPUVPCGVDRFCRGIAQVGSFÑNHÑZOVRAGRYCDC
\\QFVÑDCARFIGHRQRAJIRYJÑZRYCVAGVGHVCRYPYVRAHRARFJV
\\CGCRGYCEIROIGPÑOÑRYGCFDFRAQVQCQRDRAQVRAHRCORQRPV
\\C
\\\\El mismo fue encriptado utilizando cesar con clave \textbf{\~n}.
\\El texto desencriptado es el siguiente:
\\\\BUENOELSEÑORBUTTONDUDOLEREPUGNABALAIDEADEVESTIRA
\\SUHIJOCONROPADEHOMBRESIPOREJEMPLOPUDIERAENCONTRA
\\RUNTRAJEDECHICOGRANDEMUYGRANDEPODRIACORTARAQUELL
\\ALARGAYHORRIBLEBARBAYTEÑIRLASCANASASICONSEGUIRIA
\\DISIMULARLOSPEORESDETALLESYCONSERVARALGODESUDIGN
\\IDADPORNOMENCIONARSUPOSICIONSOCIALENBALTIMOREPER
\\OLABUSQUEDAAFANOSAPORLASECCIONDECHICOSFUEINUTILN
\\OENCONTROROPAADECUADAPARAELBUTTONQUEACABABADENAC
\\ERROGERBUTTONLEECHABALACULPAALATIENDACLAROESTAEN
\\SEMEJANTESCASOSLOAPROPIADOESECHARLELACULPAALATIE
\\NDAQUEEDADMEHADICHOQUETIENESUHIJOPREGUNTOELDEPEN
\\DIENTECONCURIOSIDADTIENEDIECISEISAÑOSAHPERDONEHA
\\BIAENTENDIDOSEISHORASENCONTRARALASECCIONDEJOVENE
\\SENELSIGUIENTEPASILLOELSEÑORBUTTONSEALEJOCONAIRE
\\TRISTEDEREPENTESEPARORADIANTEYSEÑALOCONELDEDOHAC
\\IAUNMANIQUIDELESCAPARATEAQUELEXCLAMOMELLEVOESETR
\\AJEELQUELLEVAELMANIQUIELDEPENDIENTELOMIROASOMBRA
\\DOPEROHOMBREPROTESTOESENOESUNTRAJEPARACHICOSPODR
\\IAPONERSELOUNCHICOSIPEROESUNDISFRAZTAMBIENSELOPO
\\DRIAPONERUSTEDENVUELVAMELOINSISTIOELCLIENTENERVI
\\OSOESLOQUEBUSCABAELSORPRENDIDODEPENDIENTEOBEDECI
\\O
\\\\\\El tercer texto:
\\\\NXMAUOVWRBDNMZHRRYÑUJSFOPQCJODHLMHGCHUVNAEÑVNEVF
\\DEXSTPUNZXDRMEMZSWEUUIQFTQUQTJOEAONSDWVFDHYECJQP
\\RNLZDSFGNEZJPSBDTHGCSUPRXSXWXRRALBJSGBNFVJWGJLMH
\\RWZUPDCAYRBGEOPOTINGQVRUÑTJBPIUERLXSVOFOEFVYPZTE
\\YOEOMHFOBEDSCKLCHGXNOSZQTBHSVLAHQUTUVDBIYIQTNUÑD
\\BQGSYGTJPQNDTOQNZHVDUNTDFQFUEOLOYSXNZVUDMEÑZUORV
\\DSTVPGNOGSFDUPDSZFZLXSNLWWÑTGYUOUOYHGTMJVDMEYOPC
\\DYVWAVTDOQENLRNRMGDWVHRANNAHYQENWGDOEDQTRSRFDEWD
\\CGJWLPQAÑDZQAJVNTOBOXRRVDQXNOWQBUYGDBCABHPRNVSVT
\\TFHGVMDJVONXQVGXHENSMRUNCUXBJCAHNQSNFSVACJQKEZDA
\\JBMNOQJMRAYIMZNTVUÑWMAOEQOKYHBNLQJQIGKHGXTPAUSMY
\\ÑOLOXPHULCRBMEGBXKSMRWVFTBUVGZXSAABOEGAUOSVTPWZH
\\ZHLIJYEDRQTUUOMESJYQRFSZJNPINTVWRGMESOÑGJFHWMOCJ
\\QGCGHXXRWJSCJKDGJOÑJXVRMXBJHAXNGKOPPXSCJQCEÑHHME
\\UJÑKCUUANTDOÑCAUEONNWOÑKSFLDCEÑOZCTCRBJLCJQIMUUR
\\JNAKQEZYPIXSXWXNZVUDBSPFHGRGDBXDPGQEYUGSTVPHGKSO
\\ÑDDNMSFERFHGJCGGICKYKJVDPSZGCNRIJNARBOUYHHCAYZBU
\\HYUWXDTQBUPFRHUABOFCHMRKNCSSHOUYVQDIODPGCJVSUPWS
\\NFGNSOAABSEFVMHZTINGBFVUUSVAPBHOGXHZXSSJYGUJVOVA
\\CJQNVNWGJTPRQOGZLXJRXSNSMYDZCUDOZKRLXSMIEINOTCDR
\\NLMEHGJÑDHQEYIBWEKRQXDPOXKNCRENRABBSMCHGXNTENURM
\\SDALMQNNCYOSGIÑD
\\\\El mismo fue encriptado utilizando vigenre con clave \textbf{jamoncrudo}.
\\El texto desencriptado es el siguiente:
\\\\EXAMINECONUNALUPAELGASTADOLOMOYLASTAPASYRECHACEL
\\APOSIBILIDADDEALGUNARTIFICIOCOMPROBEQUELASPEQUEÑ
\\ASILUSTRACIONESDISTABANDOSMILPAGINASUNADEOTRALAS
\\FUIANOTANDOENUNALIBRETAALFABETICAQUENOTARDEENLLE
\\NARNUNCASEREPITIERONDENOCHEENLOSESCASOSINTERVALO
\\SQUEMECONCEDIAELINSOMNIOSOÑABACONELLIBRODECLINAB
\\AELVERANOYCOMPRENDIQUEELLIBROERAMONSTRUOSODENADA
\\MESIRVIOCONSIDERARQUENOMENOSMONSTRUOSOERAYOQUELO
\\PERCIBIACONOJOSYLOPALPABACONDIEZDEDOSCONUÑASSENT
\\IQUEERAUNOBJETODEPESADILLAUNACOSAOBSCENAQUEINFAM
\\ABAYCORROMPIALAREALIDADPENSEENELFUEGOPEROTEMIQUE
\\LACOMBUSTIONDEUNLIBROINFINITOFUERAPAREJAMENTEINF
\\INITAYSOFOCARADEHUMOALPLANETARECORDEHABERLEIDOQU
\\EELMEJORLUGARPARAOCULTARUNAHOJAESUNBOSQUEANTESDE
\\JUBILARMETRABAJABAENLABIBLIOTECANACIONALQUEGUARD
\\ANOVECIENTOSMILLIBROSSEQUEAMANODERECHADELVESTIBU
\\LOUNAESCALERACURVASEHUNDEENELSOTANODONDEESTANLOS
\\PERIODICOSYLOSMAPASAPROVECHEUNDESCUIDODELOSEMPLE
\\ADOSPARAPERDERELLIBRODEARENAENUNODELOSHUMEDOSANA
\\QUELESTRATEDENOFIJARMEAQUEALTURANIAQUEDISTANCIAD
\\ELAPUERTASIENTOUNPOCODEALIVIOPERONOQUIERONIPASAR
\\PORLACALLEMEXICO

\section{Conclusi\'on}
A pesar de que \'estos m\'etodos de encriptaci\'on pudieron tener alguna utilidad en el pasado, actualmente son bastante d\'ebiles ya que existe suficiente poder de c\'omputo para romper cualquiera de \'estos por fuerza bruta, y el hecho de que varias propiedades del mensaje original persistan en el mensaje cifrado abre la puerta a ataques basados en estad\'isticas del lenguaje.
\\Si hoy en d\'ia uno tuviera que cifrar un mensaje cuyo secreto se quiere preservar, no usar\'ia ninguno de estos m\'etodos.
\end{document}